package cn.nicklemay.interview.algorithm;

public class QuickSort
{
    public static void sort(int[] a)
    {
        sort(a, 0, a.length-1);
    }

    public static void sort(int[] a, int l, int h)
    {
        if (h <= l)
        {
            return;
        }
        int j = partition(a, l, h);
        sort(a, l, j-1);
        sort(a, j+1, h);
    }

    private static int partition(int[] a, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        int p = a[lo];
        while (true)
        {
            while (a[++i] < p && i < hi)
            {
            }
            while (p < a[--j] && j > lo)
            {
            }
            if (i >= j)
            {
                break;
            }
            swapAt(a, i, j);
        }
        swapAt(a, lo, j);
        return j;
    }

    private static void swapAt(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args)
    {
        int[] a = {5, 5, 8, 4, 3, 7, 9, 2};
        sort(a);
        for(int i : a)
        {
            System.out.print(i + " ");
        }
    }

}
